// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-02 23:43
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class NumSubmatrixSumTargetT {
    /**
     * 元素和为目标值的子矩阵创建:
     * 前缀和 + Hash优化
     */
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int m = mat.length, n = mat[0].length, ans = 0;
        boolean isRight = n > m;
        for (int top = 1; top <= (isRight ? m : n); top++) {
            int[] sum = new int[(isRight ? n : m) + 1];
            Arrays.fill(sum, 0);
            for (int bot = top; bot <= (isRight ? m : n); bot++) {
                Map<Integer, Integer> map = new HashMap<>();
                int a = 0;
                for (int i = 1; i <= (isRight ? n : m); i++) {
                    sum[i] += isRight ? mat[bot - 1][i - 1] : mat[i - 1][bot - 1];
                    a += sum[i];
                    if (a == t) {
                        ans++;
                    }
                    if (map.containsKey(a - t)) {
                        ans += map.get(a - t);
                    }
                    map.put(a, map.getOrDefault(a, 0) + 1);
                }
            }
        }
        return ans;
    }
}
